/*
 * @lc app=leetcode.cn id=117 lang=csharp
 *
 * [117] 填充每个节点的下一个右侧节点指针 II
 */

// @lc code=start
/*
// Definition for a Node.
public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
*/

public class Solution {
    public Node Connect(Node root) {
        if (root == null) return null;
        Node cur = root;
        while (cur != null) {
            Node dummy = new Node(0); // 创建一个新的节点dummy，用于临时存储下一层的头节点。
            Node pre = dummy;
            while (cur != null) {
                if (cur.left != null) {
                    pre.next = cur.left;
                    pre = pre.next;
                }
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                cur = cur.next; // 通过这里从左节点 移到 右节点
            }
            cur = dummy.next; // 通过这里从左节点 移到 右节点
        }
        return root;
    }
}

/* 
    cur = 1
    dummy = null
    pre = dummy
    
    pre.next = 2
    pre = 2
    
    cur.right = 3 != null
    pre.next = 3 -> 2.next = 3
    pre = 3
    
    cur = cur.next = null
    break
    
    cur = dummy.next = 2
    
    
*/
// @lc code=end

